package LeetCode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Code581_findUnsortedSubarray {
    // 排序后比较
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length <= 1){
            return 0;
        }
        int[] new_nums = nums.clone();
        Arrays.sort(new_nums);
        int left = 0;
        while (left < nums.length){
            if (new_nums[left] != nums[left]){
                break;
            }
            left++;
        }
        int right = nums.length - 1;
        while (right >= 0){
            if (new_nums[right] != nums[right]){
                break;
            }
            right--;
        }
        return left < right ? right - left + 1 : 0;
    }
    // 单调栈
    public int findUnsortedSubarray2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        Deque<Integer> stack = new LinkedList<>();
        int leftBound = nums.length - 1;
        int rightBound = 0;
        for (int i = 0; i < nums.length; i++) {
            if (stack.isEmpty() || nums[i] >= nums[stack.peek()]){
                stack.push(i);
            } else {
                leftBound = Math.min(leftBound, stack.pop());
                i--;
            }
        }
        stack.clear();
        for (int i = nums.length-1; i >= 0; i--) {
            if (stack.isEmpty() || nums[i] <= nums[stack.peek()]){
                stack.push(i);
            } else {
                rightBound = Math.max(rightBound, stack.pop());
                i++;
            }
        }
        return rightBound > leftBound ? rightBound - leftBound + 1 : 0;
    }

    public static void main(String[] args) {
        Code581_findUnsortedSubarray code581_findUnsortedSubarray = new Code581_findUnsortedSubarray();
        System.out.println(code581_findUnsortedSubarray.findUnsortedSubarray2(new int[]{1,2,3,4}));
    }
}
